package sun.scheduler.util.collections;

import java.util.Arrays;
import java.util.Comparator;

/**
 * A fast array based fibonnachi heap implementation. That allows for
 * the data swapping process to be overwritten.
 * You may specify the initial capacity needed in the constructor to increase
 * performance.
 * 
 * @param <E> th generic data content
 * @author mfj
 */
public class Heap<E>
{
    /*
     * The default number of storable nodes.
     */

    public final static int DEFAULT_CAPACITY = 16;
    protected E[] queue;
    protected int size = 0;
    protected final Comparator<? super E> comparator;


    /**
     * Instantiates a new {@see Heap} with the specified initial capacity in the 
     * order defined by a comparator {@code Comparator<E>}
     * @param initialCapacity the initial capacity
     * @param comparator the comparator used
     */
    public Heap(int initialCapacity,
                Comparator<? super E> comparator)
    {
        if (initialCapacity < 0)
            throw new IllegalArgumentException();
        this.comparator = comparator;
        this.queue = (E[]) new Object[initialCapacity];
    }


    /**
     * Instantiates a new {@see Heap} with the default initial capacity in the 
     * order defined by a comparator {@code Comparator<E>}
     * @param comparator the comparator used
     */
    public Heap(Comparator<? super E> comparator)
    {
        this(DEFAULT_CAPACITY, comparator);
    }


    /**
     * Instantiates a new {@see Heap} which uses the specified array as heap.
     * @param array 
     * @param comparator the comparator used
     */
    public Heap(E[] array, Comparator<E> comparator)
    {
        this.queue = array;
        this.size = queue.length;
        this.comparator = comparator;

        // ensure heap property
        for (int i = (size >>> 1) - 1; i >= 0; i--)
        {
            E data = queue[i];
            if (data == null)
                throw new NullPointerException();

            heapifyDown(i, data);
        }
    }


    /**
     * Increases the capacity of this heap.
     */
    protected void increaseCapacity()
    {
        if (queue.length == Integer.MAX_VALUE)
            throw new OutOfMemoryError();

        int capacity;
        if (queue.length < 2024)
            capacity = (queue.length + DEFAULT_CAPACITY) * 2;
        else
            capacity = (queue.length + 1) * 3 / 2;

        if (capacity < 0) // integer overflow
            capacity = Integer.MAX_VALUE;

        queue = Arrays.copyOf(queue, capacity);
    }


    /**
     * Adds new that to this heap.
     * @param data the data to add.
     */
    public void add(E data)
    {
        if (data == null)
            throw new NullPointerException();

        if (size >= queue.length)
            increaseCapacity();

        if (size == 0)
            queue[0] = data;
        else
            heapifyUp(size, data);
        size++;
    }


    /**
     * Retrieves but does not remove the smales element within this heap.
     * @return the smalest element or {@code null} if the heap is empty.
     */
    public E peek()
    {
        return size == 0 ? null : queue[0];
    }


    /**
     * Gets the size of this heap.
     * @return the heap size.
     */
    public int size()
    {
        return size;
    }


    /**
     * Retrieves and removes the smales element within this heap.
     * @return the smalest element or {@code null} if the heap is empty.
     */
    public E poll()
    {
        if (size == 0)
            return null;

        E result = queue[0];

        size--;
        E lastElement = queue[size];
        queue[size] = null;

        if (size > 0)
            heapifyDown(0, lastElement);

        return result;
    }


    /**
     * Each time some data is swaped to ensure the heap property this method
     * is called.
     * @param i the index of the first element
     * @param j the index of the second element
     * @return the new index of the i-th element {@code j}
     */
    protected int swapData(int i, int j)
    {
        E temp = queue[i];
        queue[i] = queue[j];
        queue[j] = temp;
        return j;
    }


    /**
     * Sets the element at the index i and ensures the upwart heap property.
     * @param id the index to set
     * @param data the new data content
     */
    protected void heapifyUp(int id, E data)
    {
        queue[id] = data;
        while (id > 0)
        {
            int parentId = (id - 1) >>> 1;
            if (comparator.compare(data, queue[parentId]) >= 0)
                break;

            id = swapData(id, parentId);
        }
    }


    /**
     * Sets the element at the index i and ensures the downward heap property.
     * @param id the index to set
     * @param data the new data content
     */
    protected void heapifyDown(int id, E data)
    {
        queue[id] = data;
        int half = size >>> 1;
        while (id < half)
        {
            int lId = (id << 1) + 1;
            int rId = lId + 1;
            E left = queue[lId];
            E right = queue[rId];

            int minId;
            E minChild;
            if (rId < size && comparator.compare(left, right) > 0)
            {
                minId = rId;
                minChild = right;
            }
            else
            {
                minId = lId;
                minChild = left;
            }

            if (comparator.compare(data, minChild) <= 0)
                break;

            id = swapData(id, minId);
        }
    }


    /**
     * Gets a copy of the underlying queue.
     * @return {@code Arrays.copyOf(queue, size)}
     */
    public Object[] toArray()
    {
        return Arrays.copyOf(queue, size);
    }
    
    /**
     * Removes all elements from this heap.
     */
    public void clear()
    {
        Arrays.fill(queue, null);
        size = 0;
    }
    
    /**
     * indicates wheter this {@link Heap} is empty. 
     * @return {@code true} if {@code size() == 0}, {@code false} otherwhise.
     */
    public boolean isEmpty()
    {
        return size == 0;
    }
}